program eva;
const ss='0123456789ABCDEFGHIGKLMN';
var s,inputstr:string;
    site1,site2,m,n,h,a,code:integer;
    impossible:boolean;
function rei(s:string):string;
var s1,s2:string;
    i,j,k,d,num1,num2,code:integer;
begin
  s1:='';
  d:=0;
  for i:=1 to length(s) do
    begin
      num1:=pos(copy(s,i,1),ss)-1;
      num2:=pos(copy(s,length(s)-i+1,1),ss)-1;
      k:=num1+num2+d;
      d:=k div n;
      s2:=copy(ss,(k mod n)+1,1);
      s1:=s2+s1;
    end;
  if d>0 then
    begin
      s2:=copy(ss,d+1,1);
      s1:=s2+s1;
    end;
  rei:=s1;
end;
function shinji(s:string):boolean;
var i:integer;
begin
  shinji:=false;
  for i:=1 to length(s) do
    begin
      if s[i]<>s[length(s)-i+1] then
       begin
         shinji:=true;
         exit;
       end;
    end;
end;
begin
  readln(inputstr);
  site1:=pos('N=',inputstr)+2;
  site2:=pos('M=',inputstr)+2;
  val(copy(inputstr,site1,site2-3-site1),n,code);
  s:=copy(inputstr,site2,length(inputstr)-site2+1);
  if not shinji(s) then
    begin
      writeln('STEP=',0);
    end
  else
   begin
    impossible:=true;
    for h:=1 to 30 do
      begin
        s:=rei(s);
        if not shinji(s) then
          begin
            impossible:=false;
            writeln('STEP=',h);
            break;
          end;
      end;
    if impossible then
      writeln('Inpossible');
   end;

end.       head:=d+1;
        end;
      inc(d);
    end;
  rei;
  for d:=1 to n do
    begin
      if a[d,2]>maxl then
         begin
           maxl:=a[d,2];
           site2:=d;
         end;
    end;
  writeln(maxl);
  writeln(shinji);
end.
